package questions.leetcode;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import questions.model.Interval;
import questions.model.Point;
import sort.HeapSort;
import sort.MergeSort;

import common.DataPrinter;

import datastructure.list.ListNode;
import datastructure.list.ListNodeT;
import datastructure.tree.TreeNode;

/**
 *
 *@Class Name: Leetcode
 *@author: wxu on Jul 31, 2014
 *
 */
public class Leetcode {
	
	/**Interleaving String 
	 * https://oj.leetcode.com/problems/interleaving-string/
	 * @param s1
	 * @param s2
	 * @param s3
	 * @return
	 */
	public boolean isInterleave(String s1, String s2, String s3) {
        return isInterleave(s1, 0,s2, 0, s3, 0);
    }
	
	private boolean isInterleave(String s1, int from1, String s2, int from2, String s3, int from3) {
        if( from3 == s3.length()){
        	if(from1 == s1.length() && from2 ==s2.length()) return true;
        	else return false;
        }
        
        boolean result = false;
        char ch = s3.charAt(from3);
        if(from1 < s1.length() && ch == s1.charAt(from1)){
        	result = result || isInterleave(s1, from1 + 1, s2, from2, s3, from3 + 1);
        }
        
        if(from2 < s2.length() && ch == s2.charAt(from2)){
        	result = result || isInterleave(s1, from1, s2, from2+1, s3, from3 + 1);
        }
        
        return result;
    }
	
	/**
	 * https://oj.leetcode.com/problems/binary-tree-inorder-traversal/
	 * Binary Tree Inorder Traversal 
	 * @param root
	 * @return
	 */
	public List<Integer> inorderTraversal(TreeNode root) {
        return null;
    }
	
	/**
	 * https://oj.leetcode.com/problems/restore-ip-addresses/
	 * Restore IP Addresses 
	 * @param s
	 * @return
	 */
	public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<String>();
        
        restoreIpAddresses(s, 0, 1, "", result);
        
        return result;
    }
	
	private void restoreIpAddresses(String s, int from, int count, String path, List<String> result){
		if(count > 4 ){
			if( from == s.length()) result.add(path);
			else return;
		}
		
		int to = from + 1;
		if(to < s.length()){
			path = path + "." + s.substring(from, to);
			restoreIpAddresses(s, to, count + 1, path, result);
		}
		
		to = from +2;
		if(to < s.length()){
			path = path + "." + s.substring(from, to);
			restoreIpAddresses(s, to, count + 1, path, result);
		}
		
		to = from + 3;
		if(to < s.length() && Integer.valueOf(s.substring(from, to)) < 256){
			path = path + "." + s.substring(from, to);
			restoreIpAddresses(s, to, count + 1, path, result);
		}
	}
	
	/**
	 * Reverse Linked List II 
	 * https://oj.leetcode.com/problems/reverse-linked-list-ii/
	 * @param head
	 * @param m
	 * @param n
	 * @return
	 */
	public ListNode reverseBetween(ListNode head, int m, int n) {
		if(m < 0 || n < 0) throw new IllegalArgumentException("");
		
       ListNode resultHead = new ListNode(Integer.MIN_VALUE);
       ListNode resultTail = resultHead;
       ListNode tempTail = null;
       ListNode tempHead = null;
       
       int count = 0;
       while (head !=null){
    	   count ++;
    	   
    	   if( count < m){
    		   resultTail.next = head;
    		   resultTail = head;
    		   
    		   head = head.next;
    	   } else if( count == m){
    		   tempTail = head;
    		   tempHead = head;
    		   
    		   head = head.next;
    	   } else if ( count > m && count <= n){
    		   ListNode next = head.next;
    		   
    		   head.next = tempHead;
    		   tempHead = head;
    		   
    		   head = next;
    	   } else {
    		   resultTail.next = tempHead;
    		   tempTail.next = head;
    		   
    		   break;
    	   }
       }
       
       return resultHead.next;
		
    }
	
	/**
	 *  https://oj.leetcode.com/problems/subsets-ii/
	 *  Subsets II 
	 * @param num
	 * @return
	 */
	public List<List<Integer>> subsetsWithDup(int[] num) {
		HeapSort.sort(num, true);
		
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		result.add(new ArrayList<Integer>());
		
		
		for(int i = 0;i< num.length ; i++){
			if( i- 1 < 0 || num[i-1] != num[i] ) {
				List<Integer> subset = new ArrayList<Integer>();
				subset.add(num[i]);
				subset.add(i);
				
				result.add(subset);
			}
		}
		
		int start = 1;
		while(start < result.size()){
			int tempstart = result.size();
			
			for(int i = start; i< result.size(); i++){
				List<Integer> subset = result.get(start);
				int end = subset.remove(subset.size() -1);
				
				for(int ii = end + 1; ii < num.length; ii ++){
					if( ii - end -1 < 0 || num[ii-1] != num[ii]){
						List<Integer> newSubset = new ArrayList<Integer>();
						newSubset.addAll(subset);
						newSubset.add(num[ii]);
						newSubset.add(ii);
						
						result.add(newSubset);
					}
				}
			}
			
			start = tempstart;
		}
		
        return result;
    }
	
	/**https://oj.leetcode.com/problems/gray-code/
	 * Gray Code 
	 * @param n
	 * @return
	 */
	public List<Integer> grayCode(int n) {
        return null;
    }
	
	/**
	 * https://oj.leetcode.com/problems/decode-ways/
	 * Decode Ways
	 * @param s
	 * @return
	 */
	public int numDecodings(String s) {
        
		return numDecoding(s, 0);
    }
	
	private int numDecoding(String s, int from){
		if( from == s.length()) return 1;
		
		int first = s.charAt(from) - '0';
		if(first == 0) return 0;
		else if( (first == 1 || first == 2) && from + 1 < s.length() 
				&& first * 10 + (s.charAt(from +1) - '0') <=26){
			return numDecoding(s, from + 1) + numDecoding(s, from +2);
		}else return numDecoding(s, from + 1);
		
		
//		if(first >=1 && first <= 2){
//			if( from + 1 < s.length()){
//				int val = first * 10 + (s.charAt(from + 1) - '0');
//				if( val <=26){
//					return numDecoding(s, from +1) + numDecoding(s, from + 2);
//				}else{
//					return numDecoding(s, from + 1);
//				}
//			}else{
//				return numDecoding(s, from +1);
//			}
//		}else if (first >=3){
//			return numDecoding(s, from + 1);
//		}else{ // ==0
//			return 0;
//		}	
		
	}
	
	/**
	 * https://oj.leetcode.com/problems/merge-sorted-array/
	 * Merge Sorted Array
	 * @param A
	 * @param m
	 * @param B
	 * @param n
	 */
	public void merge(int A[], int m, int B[], int n) {
        int a = m-1;
        int b = n-1;
        
        int idx = m + n -1;
        for( ; idx >=0;idx --){
        	if( a < 0 || b < 0) break;
        	
        	if( A[a] < B[b]){
        		A[idx] = B[b];
        		b--;
        	}else{
        		A[idx] = A[a];
        		a--;
        	}
        }
        
        if (a < 0 ){
        	for( ; idx >=0;idx--, b--) A[idx] = b;
        }
    }
	
	/**
	 * Scramble String
	 * https://oj.leetcode.com/problems/scramble-string/
	 * @param s1
	 * @param s2
	 * @return
	 */
	public boolean isScramble(String s1, String s2) {
       return false; 
    }
	
	/**
	 * Partition List 
	 * https://oj.leetcode.com/problems/partition-list/
	 * @param head
	 * @param x
	 * @return
	 */
	public ListNode partition(ListNode head, int x) {
        ListNode head1 = new ListNode(Integer.MIN_VALUE);
        ListNode tail1 = head1;
        ListNode head2 = new ListNode(Integer.MIN_VALUE);
        ListNode tail2 = head2;
        
        while( head != null){
        	if( head.val < x){
        		tail1.next = head;
        		tail1 = head;
        	}else{
        		tail2.next = head;
        		tail2 = head;
        	}
        	
        	head = head.next;
        }
        
        tail1.next = head2.next;
        
        return head1.next;
    }
	
	/**Maximal Rectangle 
	 * https://oj.leetcode.com/problems/maximal-rectangle/
	 * @param matrix
	 * @return
	 */
	public int maximalRectangle(char[][] matrix) {
        return -1;
    }
	
	/**Largest Rectangle in Histogram
	 * https://oj.leetcode.com/problems/largest-rectangle-in-histogram/
	 * @param height
	 * @return
	 */
	public int largestRectangleArea(int[] height) {
        return -1;
    }
	
	/**https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
	 * Remove Duplicates from Sorted List II 
	 * @param head
	 * @return
	 */
	public ListNode deleteDuplicates2(ListNode head) {
		ListNode result = new ListNode(Integer.MIN_VALUE);
		ListNode tail = result;
		
		ListNode current = head;
		ListNode next = head.next;
		int count = 1;
		
		while( next != null){
			if(next.val == current.val){
				count ++;
			}else {
				if( count == 1){
					tail.next = current;
					tail = current;
				}else{
					count = 1;
				}
				
				current = next;
			}
			
			next = next.next;
		}
		
		return result.next;
    }
	
	/**https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list/
	 * Remove Duplicates from Sorted List 
	 * @param head
	 * @return
	 */
	public ListNode deleteDuplicates(ListNode head) {
		ListNode tail = head;
		ListNode next = head.next;
		
		while(next !=null){
			if(next.val == tail.val){
				continue;
			}else{
				tail.next = next;
				tail = next;
			}
			
			next = next.next;
		}
		
        return head;
    }
	
	/**https://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/
	 * Search in Rotated Sorted Array II 
	 * @param A
	 * @param target
	 * @return
	 */
	public boolean searchRotatedArray2(int[] arr, int target) {
		
        return searchRotatedArray2(arr, 0, arr.length -1, target);
    }
	
	private boolean searchRotatedArray2(int[] arr, int from, int to, int target){
		if( from > to ) return false;
		if(from == to ){
			if(arr[from] == target) return true;
			else return false;
		}
		
		int mid = from + (to -from ) /2;
		
		if( arr[mid] == target ) return true;
		else if(target > arr[mid] ){
			if( target == arr[to]) return true;
			else if( target > arr[to]) return searchRotatedArray2(arr, from, mid -1, target);
			else return searchRotatedArray2(arr, mid + 1, to, target);
		}else{
			if( target == arr[from]) return true;
			else if( target > arr[from]) return searchRotatedArray2(arr, from, mid -1, target);
			else return searchRotatedArray2(arr, mid + 1, to, target);
		}
	}
	
	/**https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
	 * Remove Duplicates from Sorted Array II 
	 * @param A
	 * @return
	 */
	public int removeDuplicates2(int[] arr) {
		
		int previous = arr[0];
		int count = 1;
		int offset = 0;
		
		for(int i = 1; i< arr.length ; i++){
			if(arr[i] == previous) {
				count ++;
			}else{
				if(count > 2) offset = offset + count -2;
				
				count = 1;
				previous = arr[i];
			}
			
			arr[i - offset] = arr[i];
		}
		
        return arr.length - offset;
    }
	
	/**https://oj.leetcode.com/problems/word-search/
	 * Word Search
	 * @param board
	 * @param word
	 * @return
	 */
	public boolean exist(char[][] board, String word) {
		for(int i = 0;i< board.length ; i++)
			for(int j = 0; j< board[0].length ; j++){
				char ch = board[i][j];
				if(ch != word.charAt(0)) continue;
				else {
					boolean hasMatch = hasMatch(board, new Point(i, j), word, new ArrayList<Point>());
					
					if(hasMatch) return true;
				}
			}
        return false;
    }
	
	private boolean hasMatch(char[][] board, Point loc, String rest, List<Point> visited){		
		if(loc.x == board.length || loc.y == board[0].length) return false;
		
		if( visited.contains(loc)) return false;
		
		char ch = board[loc.x][loc.y];
		if(ch == rest.charAt(0)){
			if(rest.length() == 1) return true;
			else{
				List<Point> newList = new ArrayList<Point>();
				newList.addAll(visited);
				newList.add(loc);
				
				return hasMatch(board, new Point(loc.x + 1, loc.y), rest.substring(1), newList) ||
					hasMatch(board, new Point(loc.x - 1, loc.y), rest.substring(1), newList) ||
					hasMatch(board, new Point(loc.x, loc.y +1), rest.substring(1), newList) ||
					hasMatch(board, new Point(loc.x - 1, loc.y -1), rest.substring(1), newList);
			}
			
		}else{
			return false;
		}
	}
	
	/**
	 * https://oj.leetcode.com/problems/subsets/
	 * Subsets 
	 * @param S
	 * @return
	 */
	public List<List<Integer>> subsets(int[] arr) {
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		
		for(int i = 0;i< arr.length;i++){
			List<Integer> list = new ArrayList<Integer>();
			list.add(arr[i]);
			list.add(i);
			result.add(list);
		}
		
		int start = 0;
		for(int i = 1; i< arr.length; i++){
			int size = result.size();
			for(int ii = start; ii < result.size() ; i++){
				List<Integer> list = result.get(ii);
				int rest = list.remove(list.size() -1);
				
				for(int iii = rest +1 ; iii < arr.length ; iii ++){
					List<Integer> newList = new ArrayList<Integer>();
					newList.addAll(list);
					newList.add(arr[iii]);
					newList.add(iii);
					
					result.add(newList);
				}		
			}
			
			start = size;
		}
		
		for( int i = start; i < result.size();i++){
			List<Integer> list = result.get(i);
			list.remove(list.size() - 1);
		}
		
        return result;
    }
	
	/**
	 * https://oj.leetcode.com/problems/combinations/
	 * Combinations 
	 * @param n
	 * @param k
	 * @return
	 */
	public List<List<Integer>> combine(int n, int k) {
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		Deque<List<Integer>> queue = new LinkedList<List<Integer>>();
		
		for(int i = 1; i<=n; i++){
			List<Integer> list = new ArrayList<Integer>();
			list.add(i);
			queue.add(list);
		}
		
		while(!queue.isEmpty()){
			List<Integer> list = queue.pollFirst();
			if(list.size() == k) result.add(list);
			else{
				int lastValue = list.get(list.size() -1);
				for(int i = lastValue + 1; i<= n; i++){
					List<Integer> newList = new ArrayList<Integer>();
					newList.addAll(list);
					queue.addLast(newList);
				}
			}
		}
		
        return result;
    }
	
	/**
	 * use the recursive way
	 * @param n
	 * @param k
	 * @param result
	 * @param temp
	 * @return
	 */
	public List<List<Integer>> combine2(int n, int k, List<List<Integer>> result, List<Integer> temp){
		 
		
		return result;
	}

	
	/**
	 * https://oj.leetcode.com/problems/minimum-window-substring/
	 * Minimum Window Substring
	 * @param S
	 * @param T
	 * @return
	 */
	public String minStringWindow(String S, String T) {
		Map<Integer, int[]> map = new Hashtable<Integer, int[]>();
		
		String result = S + S;
		
		char head = T.charAt(0);
		for(int i = 0;i< S.length();i++){
			char ch = S.charAt(i);
			if( ch == head){
				if (1 == T.length()){
					result = result.length() > 1 ? S.substring(i, i + 1) : result;
					break;
				}else{
					int[] val = {1, i};
					map.put((int)T.charAt(val[0]), val);
				}
			}else {
				if(map.containsKey((int) ch)){
					int[] val = map.get((int)ch);
					val[0] = val[0] + 1;
					if( val[0] == T.length()){
						result = result.length() > (i - val[1] + 1) ? S.substring(val[1], i+1) : result;
					}else{
						map.put((int)T.charAt(val[0]), val);
					}
					
					map.remove((int)ch);
				}
			}
		}
		
		
        return result;
    }
	
	/**
	 * https://oj.leetcode.com/problems/sort-colors/
	 * Sort Colors 
	 * @param A
	 */
	public void sortColors(int[] arr) {
		int i=-1, j=-1, k=-1;
		
		for(int p = 0;p< arr.length;p++){
			switch(arr[p]){
			case 0:
				arr[++k] = 2;
				arr[++j] = 1;
				arr[++i] = 0;
				break;
			case 1:
				arr[++k] = 2;
				arr[++j] = 1;
				break;
			case 2:
				arr[++k] = 2;
				break;
			default:
				throw new IllegalArgumentException("input has other numbers");
			}
		}
    }
	
	/**
	 * Search a 2D Matrix
	 * https://oj.leetcode.com/problems/search-a-2d-matrix/
	 * @param matrix
	 * @param target
	 * @return
	 */
	public boolean searchMatrix(int[][] matrix, int target) {
		int row = 0;
		int col = 0;
		
		for( ; row < matrix.length; row ++){
			if( target < matrix[row][0]) continue;
			else if( target == matrix[row][0]) return true;
			else break;
		}
		
		row--;
		if( row < 0) return false;
		
		for( ; col < matrix[row].length; col ++){
			if(target < matrix[row][col]) continue;
			else if(target == matrix[row][col]) return true;
			else return false;
		}
		
		return false;
    }
	
	/**
	 * Set Matrix Zeroes 
	 * https://oj.leetcode.com/problems/set-matrix-zeroes/
	 * @param matrix
	 */
	public void setZeroes(int[][] matrix) {
        
    }
	
	/**
	 * https://oj.leetcode.com/problems/edit-distance/
	 * Edit Distance
	 * @param word1
	 * @param word2
	 * @return
	 */
	public int minDistance(String word1, String word2) {
        return -1;
    }
	
	/**
	 * Simplify Path
	 * https://oj.leetcode.com/problems/simplify-path/
	 * @param path
	 * @return
	 */
	public String simplifyPath(String path) {
		
		
		List<String> folders = new ArrayList<String>();
		int from = 1;
		for(int i = from;i<path.length();i++){
			
			while(i < path.length() && path.charAt(i) != '/') i++;
			
			String folder = path.substring(from, i);
			if(folder.equals(".")){
				continue;
			}else if (folder.equals("..")){
				if(folders.size() == 0 ) throw new IllegalArgumentException("invalid path");
				else folders.remove(folders.size() -1);
			}else{
				folders.add(folder);
			}
			
			from = i +1;
		}
		
		StringBuilder result = new StringBuilder();
		result.append("/");
		for(String folder : folders){
			result.append(folder).append("/");
		}
		
		return result.toString();   
    }
	
	/**
	 * Climbing Stairs
	 * https://oj.leetcode.com/problems/climbing-stairs/
	 * @param n
	 * @return
	 */
	public int climbStairs(int n) {
		if( n == 1) return 1;
		else if ( n == 2) return 2;
		
		return climbStairs(n-1) + climbStairs(n-2);
    }

	/**
	 * Sqrt(x) 
	 * https://oj.leetcode.com/problems/sqrtx/
	 * @param x
	 * @return
	 */
public int sqrt(int x) {
        return -1;
    }
	
	/**
	 * Text Justification
	 * https://oj.leetcode.com/problems/text-justification/
	 */
	public List<String> fullJustify(String[] words, int L) {
        return null;
    }
	
	/**
	 * Plus One 
	 * https://oj.leetcode.com/problems/plus-one/
	 * @param digits
	 * @return
	 */
	public int[] plusOne(int[] digits) {
		int carry = 0;
		int index = digits.length - 1;
		
		do{
			int val = digits[index] + 1 + carry;
			digits[index] = val % 10;
			carry = val / 10;
			
			index --;
		}while( carry > 0 && index >=0);
		
		if(carry > 0 ){
			int[] result = new int[digits.length + 1];
			result[0] = carry;
			for( int i = 0; i< digits.length ; i++){
				result [ i + 1] = digits[i];
			}
			
			digits = result;
		}
		
		return digits;   
    }
	
	/**
	 * Valid Number 
	 * https://oj.leetcode.com/problems/valid-number/
	 * @param s
	 * @return
	 */
	public  boolean isNumber(String s) {
        return false;
    }
	
	/**
	 * Add Binary 
	 * https://oj.leetcode.com/problems/add-binary/
	 * @param a
	 * @param b
	 * @return
	 */
	public  String addBinary(String a, String b) {
		String result = "";
		
		int len = Math.min(a.length(), b.length());
		int carry = 0;
		for(int i = len -1 ;i >= 0; i --){
			int val = a.charAt(i) + b.charAt(i) - ('0' * 2) + carry;
			result = (val % 2) + result;
			
			carry = val /2;
		}
		
		String longer = a.length() > b.length() ? a : b;
		for( int i = longer.length() -len -1; i >=0;i++){
			int val = longer.charAt(i) - '0' + carry;
			result = (val%2) + result;
			
			carry = val /2;
		}
		
		return carry == 0 ? result : carry + result;   
	}
	
	/**
	 * Merge Two Sorted Lists 
	 * https://oj.leetcode.com/problems/merge-two-sorted-lists/
	 * @param l1
	 * @param l2
	 * @return
	 */
	public  ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		ListNode result = null;
		if(l1.val > l2.val){
			result = l2;
			l2 = l2.next;
		}else{
			result = l1;
			l1 = l1.next;
		}
		
		ListNode tail = result;
		while( l1 != null || l2 != null){
			if( l1 == null){
				tail.next = l2;
				break;
			}
			
			if(l2 == null){
				tail.next = l1;
				break;
			}
			
			if( l1.val < l2.val){
				tail.next = l1;
				tail = tail.next;
				
				l1 = l1.next;
			}else{
				tail.next = l2;
				tail = tail.next;
				
				l1 = l1.next;
			}
		}
		
        return result;
    }
	
	/**
	 * Minimum Path Sum
	 * https://oj.leetcode.com/problems/minimum-path-sum/
	 * @param grid
	 * @return
	 */
	public  int minPathSum(int[][] grid) {
		MinPath min = new MinPath();
		min.sum = Integer.MAX_VALUE;
		min.path = "";
		
		minPathSum(grid, 0, 0, 0, "", min);
		
        return min.sum;
    }
	
	private  void minPathSum(int[][] grid, int x, int y, int sum, String path, MinPath min ){
		if(x == grid.length -1 && y == grid.length -1){
			sum += grid[x][y];
			if( sum < min.sum){
				min.sum = sum;
				min.path = path + "-" + x + ", " + y;
			}
			
			return ;
		}
		
		sum += grid[x][y];
		path += "-" + x + "," + y;
		if(x < grid.length - 1) minPathSum(grid, x+1, y, sum, path, min);
		
		if(y < grid[0].length - 1) minPathSum(grid, x, y+1, sum, path, min);
	}
	
	private  class MinPath{
		int sum;
		String path;
	}
	
	/**
	 * Unique Paths II
	 * https://oj.leetcode.com/problems/unique-paths-ii/
	 * @param obstacleGrid
	 * @return
	 */
	public  int uniquePathsWithObstacles(int[][] obstacleGrid) {
        return walkPath(obstacleGrid, 0, 0, "");
    }
	
	private  int walkPath(int[][] grid, int x, int y, String path){
		if( x == grid.length-1 && y == grid[0].length -1){
			path += "-" + x + ", " + y;
			_log.append(path).append("\n");
			return 1;
		}
		
		if(grid[x][y] == 1) return 0;
		
		int result = 0;
		if(x < grid.length -1) result += walkPath(grid, x + 1, y, path );
		
		if(y < grid[0].length -1) result += walkPath(grid, x, y+1, path);
		
		return result;
	}
	
	/**
	 * Unique Paths
	 * https://oj.leetcode.com/problems/unique-paths/
	 * @param m
	 * @param n
	 * @return
	 */
	public  int uniquePaths(int m, int n) {
        return walkPath(1, 1, m, n, "");
    }
	
	private  int walkPath(int x, int y, int m, int n, String path){
		if( x == m && y == n) {
			path += "-"+ m + ", " +n;
			_log.append(path).append("\n");
			return 1;
		}
		
		int result = 0;
		if(x < m) result += walkPath(x+1, y, m, n, path + "-" + x + ", " + y);
		
		if(y < n) result += walkPath(x, y+1, m, n, path + "-" + x + ", " + y);
		
		return result ; 
	}
	
	/**
	 * Rotate List
	 * https://oj.leetcode.com/problems/rotate-list/
	 * @param head
	 * @param n
	 * @return
	 */
public  ListNodeT rotateRight(ListNodeT head, int n) {
        return null;
    }
	
	/**
	 * Permutation Sequence
	 * https://oj.leetcode.com/problems/permutation-sequence/
	 * @param n
	 * @param k
	 * @return
	 */
public  String getPermutation(int n, int k) {
        return null;
    }
	
	/**
	 * Spiral Matrix II
	 * https://oj.leetcode.com/problems/spiral-matrix-ii/
	 * @param n
	 * @return
	 */
	public  int[][] generateMatrix(int n) {
		int[][] result = new int[n][n];
		
		int cycle = n/2;
		int number = 1;
		for( int i = 0 ; i < cycle; i ++){
			
			for(int ii = cycle; ii < n - cycle; ii ++){
				result[cycle][ii] = number;
				number ++;
			}
			
			for(int ii = cycle + 1; ii < n - cycle; ii ++){
				result[ii][n- cycle -1] = number;
				number ++;
			}
			
			for(int ii = n - cycle -1 -1; ii >=cycle; ii --){
				result[n-cycle -1][ii] = number;
				number ++;
			}
			
			for(int ii = n - cycle - 2; ii >=cycle; ii --){
				result[ii][cycle] = number;
				number ++;
			}
		}
		
		return result;
	}
	
	/**
	 * Length of Last Word
	 * https://oj.leetcode.com/problems/length-of-last-word/
	 * @param s
	 * @return
	 */
public  int lengthOfLastWord(String s) {
        return -1;
    }
	
	/**
	 * Insert Interval
	 * https://oj.leetcode.com/problems/insert-interval/
	 * @param intervals
	 * @param target
	 * @return
	 */
	public  List<Interval> insert(List<Interval> intervals, Interval target) {
		
		int idx = 0;
		while( idx < intervals.size()){
			Interval cur = intervals.get(idx);
			if(target.start < cur.start){
				if( target.end < cur.start){
					intervals.add(idx, target);
					return intervals;
				}else{
					cur.start = target.start;
					cur.end = Math.max(target.end, cur.end);
					target = cur;
					break;
				}
			}else if(target.start <= cur.end){
				cur.end = Math.max(target.end, cur.end);
				target = cur;
				break;
			}else ; //continue looking
			
			idx ++;
		}
		
		if(idx == intervals.size()) {
			intervals.add(target);
			return intervals;
		}else {
			for ( int i = idx + 1; i < intervals.size(); i++){
				Interval cur = intervals.get(i);
				if( target.end < cur.start) break;
				else {
					cur.end = Math.max(target.end, cur.end);
					intervals.remove(i);
					i--;
				}
			}
		}
        return intervals;
    }
	
	/**
	 * Merge Intervals
	 * https://oj.leetcode.com/problems/merge-intervals/
	 * @param intervals
	 * @return
	 */
	public  List<Interval> merge(List<Interval> intervals) {
		
		MergeSort<Interval> sort = new MergeSort<Interval>(new Comparator<Interval>(){
			@Override
			public int compare(Interval o1, Interval o2) {
				if(o1.start < o2.start) return -1;
				else return 1;
			}
		});
		
		Interval[] arr = intervals.toArray(new Interval[]{});
		sort.sort(arr, new Interval[arr.length], true);
		
		Interval last = arr[0];
		List<Interval> result = new ArrayList<Interval>();
		result.add(last);
		for( int i =1; i< arr.length;i++){
			Interval next = arr[i];
			if(next.start <= last.end){
				 last.end = Math.max(next.end, last.end);
			}else {
				last = next;
				result.add(next);
			}
		}
		
		
        return result;
    }
	
	/**
	 * Jump Game
	 * https://oj.leetcode.com/problems/jump-game/
	 * @param A
	 * @return
	 */
	public  boolean canJump(int[] arr) {
		
		int jumpRange = 0;
		for(int i = 0;i< arr.length;i++){
			if( i > jumpRange) return false;
			if(arr[i] + i > jumpRange) {
				jumpRange = arr[i] + i;
				
				if(jumpRange >= arr.length) return true;
			}
		}
		
        return true;
    }
	
	/**
		 * Spiral Matrix
		 * https://oj.leetcode.com/problems/spiral-matrix/
		 * @param matrix
		 * @return
		 */
	public  List<Integer> spiralOrder(int[][] matrix) {
			List<Integer> result = new ArrayList<Integer> ();
			
			int row = matrix.length, col = matrix[0].length;
			int cycle = Math.min(row, col) /2;
			for( int i = 0;i< cycle;i ++){
				
				for(int idx= cycle ; idx < col - cycle; idx ++)  result.add(matrix [cycle][idx]);
				
				for(int idx = cycle + 1; idx < row -cycle; idx ++) result.add(matrix[idx][col -cycle -1]);
				
				for(int idx = col - cycle -2; idx >= cycle; idx --) result.add(matrix[row - cycle - 1][idx]);
				
				for(int idx = row - cycle -2; idx >= cycle; idx --) result.add(matrix[idx][cycle]);
				
			}
			
			if (Math.min(row, col)% 2 == 1){
				if(row > col){
					for(int idx = cycle; idx < col - cycle; idx ++) result.add(matrix[cycle][idx]);
				}else if ( row < col){
					for(int idx = cycle; idx < row -cycle; idx ++) result.add(matrix[idx][col -cycle -1]);
				}
			}
			
	        return result;
	    }

	/**
	 * Maximum Subarray
	 * https://oj.leetcode.com/problems/maximum-subarray/
	 * @param A
	 * @return
	 */
	public  int maxSubArray(int[] arr) {
		
		int max = Integer.MIN_VALUE;
		int[] result = {0, 0};
		
		int from = 0;
		int sum = 0;
		for( int i =0;i< arr.length; i++){
			sum += arr[i];
			
			if( sum > max){
				result = new int[]{from, i};
				max = sum;
			}else if( sum ==0){
				from = i + 1;
				sum = 0;
			}
		}
		
		_log.append("index: " + result[0] + ", " + result[1]);
		return max;
        
    }
	
	/**
	 * 
	 * https://oj.leetcode.com/problems/n-queens/
	 * N-Queens 
	 * @param n
	 * @return
	 */
	public  int[][] solveNQueens(int n) {
        int[] result = solveNQueens(0, n, new int[n]);
        int[][] grid = new int[n][n];
        
        if(result != null){
        	for(int i = 0;i< result.length;i++){
        		grid[i][result[i]] = 1;
        	}
        }
        
		return grid;
    }
	
	private int[] solveNQueens(int row, int len, int[] occupied){
		if(row == len) return occupied;
		
		int[] rowOccupied = new int[len];
		
		for(int i = 0 ;i < row ; i ++){
			rowOccupied[i] ++;
			
			if( occupied[i] + (row - i) < len) rowOccupied[occupied[i] + row - i] ++;
			
			if(occupied[i] - (row - i) >= 0 ) rowOccupied[occupied[i] -(row - i)] ++;
		}
		
		int[] result = null;
		for(int i = 0 ; i< len ; i++){
			if( rowOccupied[i] == 0){
				int[] newOccupied = occupied.clone();
				newOccupied[row] = i;
				result = solveNQueens(row + 1, len, newOccupied);
			}
		}
		
		return result;
	}
	
	/**
	 * @deprecated
	 * @param index
	 * @param len
	 * @param occupied
	 * @param result
	 */
	private  void solveChess(int index, int len,  int[] occupied, int[][] result){
		if (index >= len )  return;
		
		int[] nextOccupied = new int[occupied.length];
		for( int i = 0; i< occupied.length ; i++){
			int val = occupied[i];
			if( (val & 4) == 4 && i-1 >=0) nextOccupied[i-1] = nextOccupied[i-1] | 4;
			
			if ((val & 2) == 2) nextOccupied[i-1] = nextOccupied[i-1] | 2;
			
			if ((val & 1)  == 1 && i + 1 < nextOccupied.length) nextOccupied[i+1] = nextOccupied[i+1] | 4;
		}
		
		for ( int i = 0;i< len; i++){
			for( int ii = 0;ii< occupied.length; ii++){
				if( occupied[ii] == 0){
					
				}
			}
		}
	}
	
	/**
	 * Pow(x, n) 
	 * https://oj.leetcode.com/problems/powx-n/
	 * @param x
	 * @param n
	 * @return
	 */
	public  double pow(double x, int n) {
        return -1;
    }
	
	/**
	 * Anagrams 
	 * https://oj.leetcode.com/problems/anagrams/
	 * @param strs
	 * @return
	 */
	public  List<String> anagrams(String[] strs) {
     return null;   
    }

	/**
	 * Rotate Image 
	 * https://oj.leetcode.com/problems/rotate-image/
	 * @param matrix
	 */
	public  void rotate(int[][] matrix) {
        int len = matrix.length;

        int cycle = len /2 ;
        int[] temp = new int[4];
        for ( int i= 0; i< cycle; i++){
        	for( int ii = cycle ; ii < len - cycle; ii ++){
        		temp[0] = matrix [cycle][ii];
        		temp[1] = matrix [ii][len -1- cycle];
        		temp[2] = matrix [len -1 - cycle][len-1 - ii];
        		temp[3] = matrix [len - 1 - ii][cycle];
        		
        		matrix [cycle][ii]  = temp[3];
        		matrix [ii][len -1- cycle]= temp[0];
        		matrix [len -1 - cycle][len-1 - ii] =temp[1] ;
        		matrix [len - 1 - ii][cycle] = temp[2];
        	}
        }
    }
	
	/**@deprecated
	 * Permutations
	 * https://oj.leetcode.com/problems/permutations/
	 * @param num
	 * @return
	 */
	public  List<List<Integer>> permuteIntArray(int[] num) {
        return null;
    }
	
	/**@
	 * Jump Game II 
	 * https://oj.leetcode.com/problems/jump-game-ii/
	 * @param A
	 * @return
	 */
	public   int jump2(int[] arr) {
        int range = arr[0];
        int maxJump = 0;
        int jump = 1;
        
        for( int i= 0;i< arr.length;i++){
        	if( i < range)
        	if(arr[i] + i > maxJump){
        		maxJump = arr[i] + i;
        	}else if (i > range){
        		return -1;
        	}else{
        		range = maxJump;
        		jump ++;
        	}
        }
        
		return jump + 1;
    }
	
	/**
	 * @deprecated
	 * https://oj.leetcode.com/problems/wildcard-matching/
	 * @param s
	 * @param p
	 * @return
	 */
	public  boolean isMatchWildCard(String s, String p) {
        return false;
    }
	
	/**
	 * 
	 * Multiply Strings
	 * https://oj.leetcode.com/problems/multiply-strings/
	 * @param num1
	 * @param num2
	 * @return
	 */
	public String multiply(String num1, String num2) {
		String result = "";
		for(int i = num2.length() -1 ;i>= 0;i--){
			int digit = num2.charAt(i) - '0';
			String level = "";
			for (int j = 0; j < num2.length() -1 - i; j++) level += "0";
			
			String product = multiplyOne(num1, digit) + level;
			result = addStringNumber(result, product);
		}
		
        return result;
    }
	
	private String multiplyOne(String num, int digit){
		if( digit < 0 || digit > 9 ) throw new IllegalArgumentException("not single digit");
			 
		String result = "";
		int carry = 0;
		for(int i = num.length() - 1 ; i >= 0 ;i--){
			int sum = (num.charAt(i) - '0') * digit + carry;
			result = sum%10 + result;
			carry = sum / 10;
		}
		
		return carry > 0 ? carry + result : result;
	}
	
	private String addStringNumber(String num1, String num2){
		String result = "";
		
		int carry = 0;
		int index = 0;
		while (true){
			int i = num1.length()-1-index, j = num2.length() -1 -index;
			if(i >=0 && j >= 0){
				int sum = num1.charAt(i) + num2.charAt(j) + carry - '0' * 2;
				result = sum%10 + result;
				carry = sum / 10;
			}else break;
			
			index ++;
		}
		
		String longer = num1.length() > num2.length()? num1 : num2;
		while(true){
			int i = longer.length() - 1 - index;
			if( i >= 0){
				int sum = longer.charAt(i) + carry - '0';
				result = sum%10 + result;
				carry = sum / 10;
			}else break;
			
			index ++;
		}
		
		return carry > 0 ? carry + result : result;
	}
	
	
	/**
	 *
	 * Trapping Rain Water 
	 * https://oj.leetcode.com/problems/trapping-rain-water/
	 * @param arr
	 * @return
	 */
	public  int trapWater(int[] arr) {
        int total = 0;
        int left = arr[0];
        int temp = 0;
        for(int i= 1;i< arr.length;i++){
        	if(arr[i] < left){
        		temp += left - arr[i];
        	}else{
        		left = arr[i];
        		total += temp;
        		
        		temp = 0;
        	}
        }
        
        temp = 0;
        int right = arr[arr.length - 1];
        for(int i = arr.length -2 ; i > left;i--){
        	if( arr[i] < right){
        		temp += right - arr[i];
        	}else {
        		right = arr[i];
        		total += temp;
        		
        		temp = 0;
        	}
        }
        
        total += temp;
        
        return total;
    }
	
	/**
	 * First Missing Positive 
	 * https://oj.leetcode.com/problems/first-missing-positive/
	 * @param A
	 * @return
	 */
	public  int firstMissingPositive(int[] arr) {
        
		int sum = 0;
		int neg = 0;
		for(int i = 0;i<arr.length;i++) 
			if(arr[i] > 0 ) sum += arr[i];
			else neg++;
		
		int dif = (arr.length + 1) * arr.length / 2 - sum;
		int avg = dif / neg;
		
		sum = 0;
		for(int i =0;i<arr.length ; i++){
			if(arr[i] <= avg) sum += arr[i];
		}
		
		return (avg + 1) * avg /2 - sum;
    }
	
	/**
	 * @deprecated
	 * Combination Sum II 
	 * https://oj.leetcode.com/problems/combination-sum-ii/
	 * @param num
	 * @param target
	 * @return
	 */
	public  List<List<Integer>> combinationSum2(int[] num, int target) {
        return null;
    }
	
	/**
	 * @deprecated
	 * Combination Sum
	 * https://oj.leetcode.com/problems/combination-sum/
	 * @param candidates
	 * @param target
	 * @return
	 */
	public  List<List<Integer>> combinationSum(int[] candidates, int target) {
        return null;
    }
	
	/**
	 * Count and Say
	 * https://oj.leetcode.com/problems/count-and-say/
	 * @param n
	 * @return
	 */
	public  String countAndSay(int n) {
		if(n == 1) return "1";
		
		String str = countAndSay(n-1);
		StringBuilder result = new StringBuilder();
		char ch = '\n';
		int count = 0;
		for(int i = 0;i<str.length();i++){
			if(str.charAt(i) == ch){
				count ++;
			}else{
				if(count > 0){
					result.append(count).append(ch);
				}
				
				ch = str.charAt(i);
				count = 1;
			}
		}
		
		result.append(count).append(ch);
		
        return result.toString();
    }
	
	/**
	 * Sudoku Solver 
	 * https://oj.leetcode.com/problems/sudoku-solver/
	 * @param board
	 */
	public void solveSudoku(char[][] board) {
        
    }
	
	/**
	 * https://oj.leetcode.com/problems/valid-sudoku/
	 * Valid Sudoku 
	 * @param board
	 * @return
	 */
	public  boolean isValidSudoku(char[][] board) {
        return false;
    }
	
	/**
	 * Search Insert Position
	 * https://oj.leetcode.com/problems/search-insert-position/
	 * @param arr
	 * @param target
	 * @return
	 */
	public  int searchInsert(int[] arr, int target) {
        return searchInsert(arr, 0, arr.length -1, target);
    }
	
	private  int searchInsert(int[] arr, int from, int to, int target){
		if(from > to){
			if( target > arr[from]) return from + 1;
			else return from;
		}
		
		int mid = from + ((to - from)/2);
		if(arr[mid] < target){
			return searchInsert(arr, mid +1, to, target);
		}else if(arr[mid] > target){
			return searchInsert(arr, from, mid-1, target);
		}else return mid;
		
	}
	
	/**
	 * Search for a Range 
	 * https://oj.leetcode.com/problems/search-for-a-range/
	 * @param A
	 * @param target
	 * @return
	 */
	public  int[] searchRange(int[] arr, int target) {
        return searchRange(arr, 0, arr.length-1, target);
    }
	
	private  int[] searchRange(int[] arr, int from, int to, int target){
		if(from > to) return new int[]{-1, -1};
		
		int mid = from + ((to - from ) /2);
		if(target == arr[mid]){
			int[] result = {mid, mid};
			while(result[0] >=0 && arr[result[0]] == target) result[0]--;
			while(result[1] < arr.length && arr[result[1]] == target) result[1] ++;
			
			return result;
		}else if( target < arr[mid]){
			return searchRange(arr, from, mid-1, target);
		}else{
			return searchRange(arr, mid+1, to, target);
		}
	}
	
	/**
	 * 
	 * Search in Rotated Sorted Array 
	 * https://oj.leetcode.com/problems/search-in-rotated-sorted-array/
	 * @param A
	 * @param target
	 * @return
	 */
	public  int searchInRotatedArray(int[] arr, int target) {
		
		return searchInRotatedArray(arr, 0, arr.length -1, target);
    }
	
	private  int searchInRotatedArray(int[] arr, int from, int to, int target){
		if(from > to) return -1;
		
		int mid = from + ((to - from) /2 );
		if(arr[mid] == target) return mid;
		else if(target < arr[mid]){
			if(target == arr[from]) return from;
			else if(target < arr[from]) return searchInRotatedArray(arr, mid+1, to, target);
			else return searchInRotatedArray(arr, from, mid-1, target);
		}else{
			if(target == arr[to]) return to;
			else if(target < arr[to]) return searchInRotatedArray(arr, mid+1, to, target);
			else return searchInRotatedArray(arr, from, mid-1, target);
		}
	}
	
	/**
	 * Longest Valid Parentheses
	 * https://oj.leetcode.com/problems/longest-valid-parentheses/
	 * @param s
	 * @return
	 */
	public  int longestValidParentheses(String s) {
		int start=0;
		int sum=0;
		int[] result = {0, 0};
		
		for(int i=0;i<s.length();i++){
			char ch = s.charAt(i);
			if(ch == '('){
				sum++;
			}else{
				sum--;
			}
			
			if(sum == 0){
				if(i- start + 1 > result[1] - result[0] + 1){
					result[0] = start;
					result[1] = i;
				}
			}else if (sum > 0){
				continue;
			}else{
				start = i+1;
				sum = 0;
			}
		}
		
		_log.append("l to r:" + DataPrinter.printArray(result));
		
		start = s.length() -1;
		sum = 0;
		for(int i=s.length()-1;i >=0;i--){
			char ch = s.charAt(i);
			if(ch == ')'){
				sum++;
			}else{
				sum--;
			}
			
			if(sum == 0){
				if(start - i + 1 > Math.abs(result[1] - result[0]) + 1){
					result[0] = i;
					result[1] = start;
				}
			}else if (sum > 0){
				continue;
			}else{
				start = i-1;
				sum = 0;
			}
		}
		_log.append("r to l:" + DataPrinter.printArray(result));
				
        return Math.abs(result[1] -result[0]) + 1;
    }
	
	/**@deprecated
	 * Next Permutation 
	 * https://oj.leetcode.com/problems/next-permutation/
	 * @param num
	 */
	public  void nextPermutation(int[] num) {
        
    }
	
	/**
	 * @deprecated
	 * Substring with Concatenation of All Words 
	 * https://oj.leetcode.com/problems/substring-with-concatenation-of-all-words/
	 * @param S
	 * @param L
	 * @return
	 */
	public  List<Integer> findSubstring(String S, String[] L) {
        return null;
    }
	
	/**
	 * Divide Two Integers
	 * https://oj.leetcode.com/problems/divide-two-integers/
	 * @param dividend
	 * @param divisor
	 * @return
	 */
	public  int divide(int dividend, int divisor) {
		if(dividend < divisor) return 0;
		
		int rank = getRank(divisor);
		
		int result = 1;
		int rest = dividend;
		while (rest > divisor){
			int r = getRank(rest);
			result = result + 1 << (r-rank);
			
			rest = rest - (divisor << (r-rank));
		}
		
		
        return result;
    }
	
	private  int getRank(int num){
		int rank2 = 1;
		for(;;rank2++) if (num >> rank2 == 0) break;
		
		return rank2;
	}
	
	/**
	 * Implement strStr() 
	 * https://oj.leetcode.com/problems/implement-strstr/
	 * @param haystack
	 * @param needle
	 * @return
	 */
	public  int strStr(String haystack, String needle) {
		
		for(int i= 0;i< haystack.length() - needle.length();i++){
			if(haystack.charAt(i) == needle.charAt(0)){
				int jj=1, ii= i+1;
				
				for(; jj< needle.length(); jj++, ii++){
					if(needle.charAt(jj) != haystack.charAt(ii)) break;
				}
				
				if(jj == needle.length()) return i;
			}else continue;
		}
		
        return -1;
    }

	/**
	 * Remove Element
	 * https://oj.leetcode.com/problems/remove-element/
	 * @param A
	 * @param elem
	 * @return
	 */
	public  int removeElement(int[] arr, int target) {
		int offset = 0;
		
		for(int i =0; i< arr.length;i++){
			if(arr[i] == target){
				offset ++;
			}else{
				arr[i - offset] = arr[i];
			}
			
		}
		
		return arr.length - offset;
    }
	
	/**
	 * Remove Duplicates from Sorted Array
	 * https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array/
	 * @param A
	 * @return
	 */
	public  int removeDuplicates(int[] arr) {
		int tail = 0;
		
		for(int i = 1;i< arr.length;i++){
			if(arr[i] == arr[tail]){
				continue;
			}else{
				tail ++;
				arr[tail] = arr[i];
			}
		}
		
		return tail + 1; 	 	
    }
	
	/**@deprecated
	 * 
	 * Reverse Nodes in k-Group
	 * https://oj.leetcode.com/problems/reverse-nodes-in-k-group/
	 * @param head
	 * @param k
	 * @return
	 */
	public   ListNodeT<Integer> reverseKGroup(ListNodeT<Integer> head, int k) {
		if( k == 1) return head;
		
		ListNodeT<Integer> ktail = head;
		ListNodeT<Integer> khead = head;
		ListNodeT<Integer> tail = null;
		ListNodeT<Integer> current = head.next;
		
		int count = 1;
		while(current != null){
			count ++;
			ListNodeT<Integer> temp = current;
			current = current.next;
			
			temp.next = khead;
			khead = temp;
			
			if( count == k){
				if(tail == null){
					head = khead;
					tail = ktail;
				}else{
					tail.next = khead;
					tail = ktail;
				}
				
				ktail = current;
				khead = current;
				

			}
		}
		
		return null;
    }
	
	
	/**
	 * Swap Nodes in Pairs
	 * https://oj.leetcode.com/problems/swap-nodes-in-pairs/
	 * 
	 * @param head
	 * @return
	 */
	public  ListNodeT<Integer> swapPairs(ListNodeT<Integer> head) {
		if( head.next == null) return head; // head is not null 
		
		ListNodeT<Integer> tail = head;
		ListNodeT<Integer> next = head.next.next ;
		head = head.next;
		
		head.next = tail;
		
		while(next != null){
			if( next.next != null){
				ListNodeT<Integer> temp = next;
				next = next.next.next;
				
				tail.next = temp;
				tail.next.next = temp.next;
				
				tail = tail.next.next;
			}else{
				tail.next = next;
				next = null;
			}
		}
		
		return head;
    }

	/**
	 * @deprecated
	 * 
	 * https://oj.leetcode.com/problems/merge-k-sorted-lists/ 
	 * Merge k Sorted Lists
	 * 
	 * @param lists
	 * @return
	 */
	public  ListNodeT mergeKLists(List<ListNodeT> lists) {
		return null;
	}
	
	/**
	 * tested 
	 * 
	 * Generate Parentheses
	 * https://oj.leetcode.com/problems/generate-parentheses/
	 * @param n
	 * @return
	 */
	public  List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        
        createParenthesis((int)Math.pow(2, n* 2)-1, "", 0, 0, result);
        return result;
    }
	
	private  void createParenthesis(int len, String str, int sum, int index, List<String> result){
		if(index > len && sum != 0) return;
		
		if(index % 2 == 0){
			str += "(";
			sum++;
		}else{
			sum --;
			if(sum < 0) return ;
			else str+=")";
		}
		
		if(index * 2 + 1 < len){
			createParenthesis(len, str, sum, index * 2 + 1, result);
		}else if(sum == 0 ) {
			result.add(str);
			return;
		}
		
		if(index * 2 + 2 < len){
			createParenthesis(len, str, sum, index * 2 + 2, result);
		}else if( sum == 0) {
			result.add(str);
		}
	}
	
    /**
     * tested 
     * 
     * Valid Parentheses
     * https://oj.leetcode.com/problems/valid-parentheses/
     * @param s
     * @return
     */
    public  boolean isValidParentheses(String s) {
        if(s.length() %2 == 1) return false;
        
        char[] stack = new char[s.length()/2];
        int size = 0 ;//exclusive
        for(int i=0;i<s.length();i++){
            char ch = s.charAt(i);
            if(ch == '(' || ch == '[' || ch == '{'){
                if(size < stack.length){
                    stack[size] = ch;
                    size++;
                }else{
                    return false;
                }
            }else{
                if(size > 0){
                    char pre = stack[size-1];
                    if((pre == '(' && ch == ')') || (pre == '[' && ch == ']') || (pre == '{' && ch == '}')){
                        size --;
                    }else{
                        return false;
                    }
                }else{
                    return false;
                }
            }

        }
        
        return size == 0? true : false;
    }
    
    /**
     * Remove Nth Node From End of List 
     * https://oj.leetcode.com/problems/remove-nth-node-from-end-of-list/
     * @param head
     * @param n
     * @return
     */
    public  ListNodeT<Integer> removeNthFromEnd(ListNodeT<Integer> head, int n) {
        
        ListNodeT<Integer> current = head.next;
        ListNodeT<Integer> tempHead = head;
        while(current != null ){
            ListNodeT<Integer> next = current.next;
            
            current.next = tempHead;
            tempHead = current;
            current = next;
        }
        
        int count = 1;
        current = tempHead.next;
        while(current != null){
            count ++;
            
            ListNodeT<Integer> next = current.next;
            if(count == n){
                current = next;
            }else{
                current.next = tempHead;
                tempHead = current;
                current = next;
            }
        }
        
        return tempHead;
    }

    /**
     * tested 
     * 
     * Letter Combinations of a Phone Number 
     * https://oj.leetcode.com/problems/letter-combinations-of-a-phone-number/
     * @param digits
     * @return
     */
    public  List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<String>();
        result.add("");
        String[] letters= {"", " ", "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        
        for(int i=0;i<digits.length();i++){
            int num = digits.charAt(i)- '0';
            if(num < 0 || num > 9) throw new NumberFormatException("worng number format");
            if(num == 0) continue;
            
            List<String> temp = new ArrayList<String>();

            for(int j=0;j< letters[num].length();j++){
                for(String res : result){
                    temp.add(res + letters[num].charAt(j));
                }
            }
            
            result = temp;
        }
        
        return result;
    }
	
	/**
	 * tested
	 * 
	 * 3Sum
	 * https://oj.leetcode.com/problems/3sum/
	 * @param arr
	 */
	public   List<int[]> threeSum(int[] arr) {
		HeapSort.sort(arr, true);
		
		int median = 0;
		for(; median < arr.length;median ++){
			if(arr[median] >= 0 ) break;
		}
		
		List<int[]> result = new ArrayList<int[]>();
		if(median == 0 || median == arr.length -1) return result; 
		
		
		for ( int i = 0;i< median; i ++){
			if(i - 1 >=0 && arr[i] == arr[i-1]){
				continue;
			}else{
				findTwoNumbers(arr, median, arr.length-1, arr[i], result);
			}
		}
		
		for ( int i = median ;i< arr.length; i ++){
			if(i - 1 >= median && arr[i] == arr[i-1]){
				continue;
			}else{
				findTwoNumbers(arr, 0, median-1, arr[i], result);
			}
		}
		
		return result;
    }
	
	private  void findTwoNumbers(int[] arr, int from, int to, int target, List<int[]> result){
		int forward = from, backward = to;
		
		while(forward < backward){
			if(arr[forward] + arr[backward] + target == 0){
				if(result.size() == 0 || result.get(result.size()-1)[0] != arr[forward]){
					_log.append("[" + arr[forward] +", " + arr[backward] +", " +target +"]");
					result.add(new int[]{arr[forward], arr[backward], target});
				}
				
				forward ++;
				backward --;
			}else if(arr[forward] + arr[backward] > target){
				backward --;
			}else{
				forward ++;
			}
		}
	}
	
	/**
	 * @deprecated
	 * ambiguous question
	 * 
	 * Longest Common Prefix
	 * https://oj.leetcode.com/problems/longest-common-prefix/
	 * @param strs
	 * @return
	 */
	public  String longestCommonPrefix(String[] strs) {
        
		return null;
    }
	
	/**
	 * tested
	 * 
	 * Roman to Integer
	 * https://oj.leetcode.com/problems/roman-to-integer/
	 * @param s
	 * @return
	 */
	public  int romanToInt(String s) {
        
		int result = 0;
		
		for(int i=0;i< s.length();i++){
			char ch = s.charAt(i);
			switch(ch){
			case 'M':
				result +=1000; break;
			case 'D':
				result +=500; break;
			case 'C':
				if(i + 1 < s.length()){
					if(s.charAt(i+1) == 'M'){
						result +=900;
						i++;
					}else if(s.charAt(i+1) == 'D') {
						result +=400;
						i++;
					}else result +=100;
				}else{
					result += 100;
				}
				break;
			case 'L':
				result +=50; break;
			case 'X':
				if(i + 1 < s.length()){
					if(s.charAt(i+1) == 'C'){
						result +=90;
						i++;
					}else if(s.charAt(i+1) == 'L') {
						result +=40;
						i++;
					}else result +=10;
				}else{
					result += 10;
				}
				break;
			case 'V':
				result +=5; break;
			case 'I':
				if(i + 1 < s.length()){
					if(s.charAt(i+1) == 'X'){
						result +=9;
						i++;
					}else if(s.charAt(i+1) == 'V') {
						result +=4;
						i++;
					}else result +=1;
				}else{
					result += 1;
				}
				break;
			default: throw new IllegalArgumentException("wrong format");
			}
		}
		
		return result;
    }
	
	/**
	 * tested
	 * 
	 * Integer to Roman
	 * https://oj.leetcode.com/problems/integer-to-roman/
	 * @param num
	 * @return
	 */
	public  String intToRoman(int num) {
		if(num > 3999) throw new IllegalArgumentException("num > 3999");
       
		StringBuilder result = new StringBuilder();
		int rest = num;

		result.append(getRoman(rest/1000, "", "", "M"));
		rest = rest%1000;
		result.append(getRoman(rest/100, "M", "D", "C"));
		rest = rest%100;
		result.append(getRoman(rest/10, "C", "L", "X"));
		rest = rest%10;
		result.append(getRoman(rest/1, "X", "V", "I"));
		
		return result.toString();
    }
	
	private  String getRoman(int d, String hig, String med, String cur) {
		switch (d) {
		case 0: return "";
		case 1: return cur;
		case 2: return cur +cur;
		case 3: return cur +cur + cur;
		case 4: return cur + med;
		case 5: return med;
		case 6: return med + cur;
		case 7: return med + cur + cur;
		case 8: return med + cur + cur + cur;
		case 9: return cur + hig;
		default:
			throw new IllegalArgumentException("too big number");
		}
	}
	
	/**
	 * Container With Most Water 
	 * https://oj.leetcode.com/problems/container-with-most-water/
	 * @param height
	 * @return
	 */
	public  int maxWaterContainter(int[] height) {
        int left = 0, right = height.length-1;
        int[] result ={0, 0};
        while(left < right){
        	if(Math.min(height[left], height[right]) * (right -left) > 
        		Math.min(height[result[0]], height[result[1]]) * (result[1] - result[0])){
        		result[0] = left;
        		result[1] = right;
        	}
        	
        	if(height[left] < height[right]){
        		left ++;
        	}else{
        		right --;
        	}
        }
        
        _log.append("lines:" + height[result[0]]+ ", "+ height[result[1]]);
        
		return Math.min(height[result[0]], height[result[1]]) * (result[1] - result[0]);
    }
	
	/**
	 * @deprecated
	 * Regular Expression Matching 
	 * https://oj.leetcode.com/problems/regular-expression-matching/
	 * @param s
	 * @param p
	 * @return
	 */
	public boolean isMatchRE(String s, String p) {
        boolean single = true;
        char ch = '.';
        
        int si=0 , pi=0;
        while(true){
        	if(si == s.length() || pi == p.length()) return false;
        	
        	ch = p.charAt(pi);
        	if(ch == '*') return false;
        	if(pi+ 1 < p.length() && p.charAt(pi+1) == '*'){
        		single = false;
        		pi +=2;
        	}else{
        		single = true;
        		pi++;
        	}
        	
        	if(single){
        		if(s.charAt(si) != ch || ch != '.') return false;
        		si++;
        	}else{
        		if(s.charAt(si) != ch || ch != '.') return false;
        		
        		si++;
        		while(si < s.length()){
        			if(s.charAt(si) != ch || ch != '.') break;
        			
        			si++;
            	}
        	}
        	
        	
        	if(si == s.length() && pi == p.length()) return true;
        }
        
		
    }
	
	/**
	 * tested: did not test the integer.max_value
	 * 
	 * Palindrome Number
	 * https://oj.leetcode.com/problems/palindrome-number/
	 * @param x
	 * @return
	 */
	public  boolean isPalindrome(int x) {
	
		try{
			int result = reverseInteger(x);
			if(result == x) return true;
			else return false;
		}catch(Exception e){
			return false;
		}
    }
	
	/**
	 * tested
	 * 
	 * String to Integer (atoi) 
	 * https://oj.leetcode.com/problems/string-to-integer-atoi/
	 * @param str
	 * @return
	 */
	public  int atoi(String str) {
		if(str == null || str.trim().isEmpty()) throw new IllegalArgumentException("empty string");
		
		boolean positive = true;
		int start = 0;
		if(str.charAt(0) =='-'){
			positive = false;
			start = 1;
		}else if (str.charAt(0) == '+'){
			positive = true;
			start = 1;
		}
		
		long result = 0;
		for(;start < str.length(); start++){
			char ch = str.charAt(start);
			if( ch >= '0' && ch <= '9'){
				result = result * 10 + (ch - '0');
				
				if(result > Integer.MAX_VALUE) throw new NumberFormatException("exceed max int value");
				else continue;
			}else{
				throw new NumberFormatException("not a number");
			}
		}
		
        
		return positive ? (int)result : -(int)result;
    }
	
	/**
	 * tested
	 * 
	 * Reverse Integer 
	 * https://oj.leetcode.com/problems/reverse-integer/
	 * @param x
	 * @return
	 */
	public  int reverseInteger(int x) {
        long result = 0;
        
        int rest = Math.abs(x);
        while(rest > 0 ){
        	int digit = rest % 10;
        	result =  result * 10  + digit;
        	if(result > Integer.MAX_VALUE){
        		throw new IllegalArgumentException("exceed max integer value");
        	}
        	
        	rest = (rest - digit) /10;
        }
        
		return x < 0 ? -(int)result : (int)result;
    }
	
	/**
	 * tested 
	 * 
	 * ZigZag Conversion
	 * https://oj.leetcode.com/problems/zigzag-conversion/
	 * @param s
	 * @param nRows
	 * @return
	 */
	public  String convertZigZag(String s, int nRows) {
        
		StringBuilder result = new StringBuilder();
		
		for(int i =0;i< nRows;i++){
			int col = 0;
			int cur = (nRows + 1) * col + i;
			while(cur < s.length()){
				result.append(s.charAt(cur));
				
				if(i == nRows/2){
					col ++;
					if((nRows + 1)* col -1 < s.length()){
						result.append(s.charAt((nRows + 1)* col -1 ));
					}
					
					cur = (nRows + 1) * col + i;
				}else{
					col ++;
					cur = (nRows + 1) * col + i;
				}
			}
			
		}
		
		return result.toString();
    }
	
	
	/**
	 * tested
	 * 
	 * Longest Palindromic Substring
	 * https://oj.leetcode.com/problems/longest-palindromic-substring/
	 * @param s
	 * @return
	 */
	public  String longestPalindrome(String s) {
        int[] result = {0, 0};
		int forward= 0, backward=0;
		
		for(int i = 0;i< s.length();i++){
			forward = i+1;
			backward = i-1;
			
			while(forward < s.length() && s.charAt(forward)==s.charAt(i)){
				forward ++;
			}
			
			while(forward < s.length() && backward >=0 && s.charAt(backward) == s.charAt(forward)){
				forward ++;
				backward --;
			}
			
			if(forward-backward > result[1]-result[0]){
				result[1]=forward;
				result[0]=backward;
			}
			
			//if(forward == s.length()) break;
		}
		
		return s.substring(result[0]+1, result[1]);
    }
	
	/**
	 * tested
	 * 
	 * Add Two Numbers
	 * https://oj.leetcode.com/problems/add-two-numbers/
	 * @param l1
	 * @param l2
	 * @return
	 */
	public ListNodeT<Integer> addTwoNumbers(ListNodeT<Integer> l1, ListNodeT<Integer> l2) {
        ListNodeT<Integer> dummy =new ListNodeT<Integer>(-1);
        ListNodeT<Integer> cur = dummy;
		
		ListNodeT<Integer> cur1 = l1;
		ListNodeT<Integer> cur2 = l2;
		int previous = 0;
		while(true){
			if(cur1 == null){
				if(cur2 == null){
					if(previous == 1) cur.next = new ListNodeT<Integer>(1);
					
					return dummy.next;
				}else{
					if(previous == 1){
						if(cur2.value + 1 >= 10){
							cur.next = new ListNodeT<Integer>( cur2.value + 1 -10);
							
							cur2 = cur2.next;
							cur = cur.next;
						}else{
							cur.next = new ListNodeT<Integer>(cur2.value + 1);
							cur.next.next = cur2.next;
							
							return dummy.next;
						}
					}else{
						cur.next = cur2;
						return dummy.next;
					}
					
				}
			}else{
				if(cur2 == null){
					if(previous == 1){
						if(cur1.value + 1 >= 10){
							
						}else{
							
						}
					}else{
						
					}
					cur.next = cur1;
					return dummy.next;
				}else{
					if(cur1.value + cur2.value > 10){
						
					}else{
						cur.next = new ListNodeT<Integer>(cur1.value + cur2.value);
					}
				}
			}
		}
	
    }
	
	/**
	 * tested
	 * 
	 * Longest Substring Without Repeating Characters 
	 * https://oj.leetcode.com/problems/longest-substring-without-repeating-characters/
	 * @param s
	 * @return
	 */
	public  int lengthOfLongestSubstring(String s) {
		Map<Integer, Integer> existed = new HashMap<Integer, Integer>();
		
		int[] range = {0, 0};
		
		int start = 0; 
		for(int i=0;i< s.length();i++){
			char ch = s.charAt(i);
			if(!existed.containsKey(new Integer(ch))){
				existed.put(new Integer(ch), new Integer(i));
			}else{
				int old = existed.get(new Integer(ch));
				if(old < start){
					existed.put(new Integer(ch), new Integer(i));
				}else{
					if(i-start > range[1]- range[0]){
						range[0] = start;
						range[1] = i;
						start = old +1;
					}else{
						start = old + 1;
					}
				}
			}
		}
		
		_log.append("range:" + range[0] +", " + range[1]);
		return range[1] - range[0];
	}
	
	/**
	 * tested
	 * 
	 * @param arr1
	 * @param arr2
	 * @param k
	 * @return
	 */
	public  int findKthNumber(int[] arr1, int[] arr2, int k){
		int p1=0, p2=0;
		
		if(arr1.length + arr2.length < k) return -1;
		
		while(true){
			while(p1 < arr1.length-1 && (p2== arr2.length-1 || arr1[p1]<= arr2[p2])){
				p1++;
				if(p1 + p2 == k-1){
					if(p2==arr2.length-1) return arr1[p1-1];
					else return Math.min(arr1[p1], arr2[p2]);
				}
			}
			
			while(p2 < arr2.length-1 && (p1== arr1.length-1 || arr2[p2]<= arr1[p1])){
				p2++;
				if(p2 + p1 == k-1){
					if(p1== arr1.length) return arr2[p2-1];
					else return Math.min(arr1[p1], arr2[p2]);
				}
			}
		}
	}
	
	/**
	 * tested
	 * 
	 * Median of Two Sorted Arrays
	 * https://oj.leetcode.com/problems/median-of-two-sorted-arrays/
	 * @param arr1
	 * @param arr2
	 * @return
	 */
	public  int findMedianSortedArrays(int[] arr1, int[] arr2){
		if((arr1.length + arr2.length)%2==0){
			int k = (arr1.length + arr2.length)/2;
			return (findKthNumber(arr1, arr2, k) +findKthNumber(arr1, arr2, k-1))/2;
		}else{
			int k = (arr1.length + arr2.length)/2;
			return findKthNumber(arr1, arr2, k);
		}
	}

	
	/**
	 * Tested
	 * 
	 * Two Sum
	 * https://oj.leetcode.com/problems/two-sum/
	 * @param arr
	 * @param target
	 * @return
	 */
	public  int[] twoSum(int[] arr, int target){
		Map<Integer, Integer> occured = new HashMap<Integer, Integer>();
		for(int i =0;i<arr.length;i++){
			if(arr[i] >= target) continue;

			Integer other = new Integer(target - arr[i]);
			if(occured.containsKey(other)){
				_log.append("values=" + other+"," + arr[i]);
				return new int[]{occured.get(other), i};
			}else{
				occured.put(new Integer(arr[i]), i);
			}
		}
		
		return new int[]{-1, -1};
	}
	
//////////////////////////////////////////////////////////////////////////////////////////////////////////
	
	private final  StringBuilder _log= new StringBuilder();
	
	public  String getLog(){
		return _log.toString();
	}

}
